class Solution:
    def maxProduct(self, s: str) -> int:
        # print("字符串长度:", len(s))

        s = "$" + s + "!"  # 加入'$'和'!'是为了循环时避免越界
        n = len(s) - 1

        dp = [0] * n
        iMax, rMax, ans = 0, 0, 0  # iMax,rMax 分别是回文中心和最远的回文右半径端点

        # Manacher算法计算每一个位置左右拓展的距离
        for i in range(1, n):
            if i <= rMax:
                dp[i] = min(rMax - i + 1, dp[2 * iMax - i])
            while s[i + dp[i]] == s[i - dp[i]]:
                dp[i] += 1
            if i + dp[i] - 1 > rMax:
                iMax = i
                rMax = i + dp[i] - 1

        # 计算从第i个位置往前可以匹配的最大长度
        prefix = [0] * n
        for i in range(n):
            right = i + dp[i] - 1
            prefix[right] = max(prefix[right], dp[i] * 2 - 1)
        for i in range(1, n):
            prefix[i] = max(prefix[i - 1], prefix[i])
        for i in range(n - 2, -1, -1):
            prefix[i] = max(prefix[i], prefix[i + 1] - 2)

        # 计算从第i个位置往后可以匹配的最大长度
        suffix = [0] * n
        for i in range(n):
            left = i - dp[i] + 1
            suffix[left] = max(suffix[left], dp[i] * 2 - 1)
        for i in range(n - 2, -1, -1):
            suffix[i] = max(suffix[i + 1], suffix[i])
        for i in range(1, n):
            suffix[i] = max(suffix[i], suffix[i - 1] - 2)

        # print(dp)
        # print(prefix)
        # print(suffix)

        ans = 0
        for i in range(1, n - 1):
            ans = max(ans, prefix[i] * suffix[i + 1])
        return ans


if __name__ == "__main__":
    print(Solution().maxProduct(s="ababbb"))  # 9
    print(Solution().maxProduct(s="zaaaxbbby"))  # 9

    # 测试用例53/67
    print(Solution().maxProduct("ggbswiymmlevedhkbdhntnhdbkhdevelmmyiwsbgg"))  # 45

    # 自制用例
    # print(Solution().maxProduct(s="aaaaaaaaaa"))  # 25
    # print(Solution().maxProduct(s="ababababab"))  # 25
